package com.leetcode.tree.bst;

import com.leetcode.basic.TreeNode;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/7/18 22:02
 */
public class FindMode_501 {

    private int curCnt = 1;
    private int maxCnt = 1;
    private TreeNode preNode = null;

    public int[] findMode(TreeNode root) {
        List<Integer> maxCntNums = new ArrayList<>();
        inOrder(root, maxCntNums);
        int[] ret = new int[maxCntNums.size()];
        int idx = 0;
        for (int num : maxCntNums) {
            ret[idx++] = num;
        }
        return ret;
    }

    private void inOrder(TreeNode node, List<Integer> nums) {
        if (node == null) return;
        inOrder(node.left, nums);
        if (preNode != null) {
            curCnt = preNode.val == node.val ? curCnt + 1 : 1;
        }
        if (curCnt > maxCnt) {
            maxCnt = curCnt;
            nums.clear();
            nums.add(node.val);
        } else if (curCnt == maxCnt) {
            nums.add(node.val);
        }
        // 保留前驱结点
        preNode = node;
        inOrder(node.right, nums);
    }

    static class Solution {

        int count = 1, maxCount = 1;
        TreeNode pre = null;

        public int[] findMode(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            inOrder(root, res);
            int[] ans = new int[res.size()];
            for (int i = 0; i < res.size(); i++) {
                ans[i] = res.get(i);
            }
            return ans;
        }

        private void inOrder(TreeNode root, List<Integer> nums) {
            if (root == null) return;
            inOrder(root.left, nums);
            if (pre != null) {
                count = pre.val == root.val ? count + 1 : 1;
            }
            if (maxCount == count)
                nums.add(root.val);
            else if (maxCount < count) {
                nums.clear();
                nums.add(root.val);
                maxCount = count;
            }
            pre = root;
            inOrder(root.right, nums);
        }

    }

}
